{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "using RegionTrees\n",
    "import StaticArrays: SVector\n",
    "using Plots"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Cell: RegionTrees.HyperRectangle{2,Float64}([0.0,0.0],[1.0,1.0])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# The most basic data type in this package is a Cell,\n",
    "# which can represent a node or a leaf in the tree.\n",
    "# Let's build a Cell which spans from [0, 0] and has\n",
    "# length 1 along each axis\n",
    "root = Cell(SVector(0., 0), SVector(1., 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "true"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# The Cell type is used for leaves and nodes. We can check\n",
    "# if root is a leaf with isleaf() \n",
    "isleaf(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Cell: RegionTrees.HyperRectangle{2,Float64}([0.0,0.0],[1.0,1.0])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Now let's refine the cell:\n",
    "split!(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "false"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# The cell is no longer a leaf because it now has children:\n",
    "isleaf(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "@assert length(children(root)) == 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Cell: RegionTrees.HyperRectangle{2,Float64}([0.0,0.0],[0.5,0.5])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Each child now represents one quarter of the region\n",
    "# spanned by root. We can access children using the\n",
    "# indexing notation:\n",
    "root[1,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Cell: RegionTrees.HyperRectangle{2,Float64}([0.0,0.0],[0.5,0.5])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# or with the children() function:\n",
    "children(root)[1,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Cell: RegionTrees.HyperRectangle{2,Float64}([0.0,0.0],[0.5,0.5])"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# We can further refine one of the children:\n",
    "split!(root[1,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Cell: RegionTrees.HyperRectangle{2,Float64}([0.0,0.0],[0.25,0.25])"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Now there are more children:\n",
    "root[1,1][1,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Cell: RegionTrees.HyperRectangle{2,Float64}([0.0,0.25],[0.25,0.25])"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "root[1,1][1,2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<img src=\"\" />"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Let's plot the cells we have so far\n",
    "plt = plot(xlim=(0, 1), ylim=(0, 1), legend=nothing)\n",
    "for leaf in allleaves(root)\n",
    "    v = hcat(collect(vertices(leaf.boundary))...)\n",
    "    plot!(plt, v[1,[1,2,4,3,1]], v[2,[1,2,4,3,1]])\n",
    "end\n",
    "plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/usr/local/lib/python2.7/site-packages/matplotlib/font_manager.py:1282: UserWarning: findfont: Font family [u'Helvetica'] not found. Falling back to Bitstream Vera Sans\n",
      "  (prop.get_family(), self.defaultFamily[fontext]))\n"
     ]
    }
   ],
   "source": [
    "# Now, so far just splitting cells is not super useful. Let's\n",
    "# try adding some data to each cell:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Cell: RegionTrees.HyperRectangle{2,Float64}([0.0,0.0],[1.0,1.0])"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cell = Cell(SVector(0., 0), SVector(1., 1), \"A\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"A\""
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# We now have a new cell, with a data payload consisting of\n",
    "# a string:\n",
    "cell.data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "RegionTrees.Cell{String,2,Float64,4}"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# The type of the data payload (String) is now part of the cell's\n",
    "# type, which lets Julia efficiently handle our cell:\n",
    "typeof(cell)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Cell: RegionTrees.HyperRectangle{2,Float64}([0.0,0.0],[1.0,1.0])"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# By default, `split!(cell)` just copies the cell's data into\n",
    "# each of its children. That's probably not what we want here.\n",
    "# Instead, we can pass in new data for each child when we call\n",
    "# split:\n",
    "split!(cell, [\"B\", \"C\", \"D\", \"E\"])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"B\""
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cell[1,1].data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"C\""
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cell[2,1].data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Cell: RegionTrees.HyperRectangle{2,Float64}([0.25,0.75],[0.25,0.25])"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# If managing a list of child data is inconvenient, you can \n",
    "# instead pass in a function to generate the child data. That\n",
    "# function will be called with two inputs: the cell being split\n",
    "# and the indices of the child being created:\n",
    "\n",
    "c = Cell(SVector(0., 0), SVector(1., 1), \"root\")\n",
    "\n",
    "# Let's make a simple data generator that just tacks on the \n",
    "# indices from the root of the tree:\n",
    "function getdata(cell, child_indices)\n",
    "    \"$(cell.data) child $(child_indices)\"\n",
    "end\n",
    "\n",
    "split!(c, getdata)\n",
    "split!(c[1,1], getdata)\n",
    "split!(c[1,2], getdata)\n",
    "split!(c[1,2][2,2], getdata)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"root child (1,2) child (2,2) child (1,1)\""
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c[1,2][2,2][1,1].data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Cell: RegionTrees.HyperRectangle{2,Float64}([0.0,0.0],[1.0,1.0])"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Finally, there is a higher-level abstraction than this\n",
    "# for automatically splitting cells and populating their data. \n",
    "# The concept is based around adaptive sampling and is implemented\n",
    "# through the \"refinery\" concept. \n",
    "#\n",
    "# A refinery is a type which inherits from AbstractRefinery and \n",
    "# implements two methods:\n",
    "#\n",
    "# needs_refinement(refinery, cell::Cell): \n",
    "#     returns true if the cell should be split\n",
    "# \n",
    "# refine_data(refinery, cell::Cell, indices): \n",
    "#     returns the new data for the cell's child with the\n",
    "#     given indices\n",
    "#\n",
    "# You may want to use child_boundary(cell, indices) to get the bounding\n",
    "# box corresponding to the child cell for which you are generating data.\n",
    "\n",
    "# Let's create a trivial example that will refine each cell until\n",
    "# its width is less than a given tolerance:\n",
    "import RegionTrees: AbstractRefinery, needs_refinement, refine_data\n",
    "\n",
    "type MyRefinery <: AbstractRefinery\n",
    "    tolerance::Float64\n",
    "end\n",
    "\n",
    "# These two methods are all we need to implement\n",
    "function needs_refinement(r::MyRefinery, cell)\n",
    "    maximum(cell.boundary.widths) > r.tolerance\n",
    "end\n",
    "function refine_data(r::MyRefinery, cell::Cell, indices)\n",
    "    boundary = child_boundary(cell, indices)\n",
    "    \"child with widths: $(boundary.widths)\"\n",
    "end\n",
    "\n",
    "# Now we can use our refinery to create the entire tree, with\n",
    "# all cells split automatically:\n",
    "r = MyRefinery(0.05)\n",
    "root = Cell(SVector(0., 0), SVector(1., 1), \"root\")\n",
    "adaptivesampling!(root, r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "\"child with widths: [0.03125,0.03125]\""
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "root[1,1][1,1][1,1][1,1][1,1].data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<img src=\"\" />"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "plt = plot(xlim=(0, 1), ylim=(0, 1), legend=nothing)\n",
    "for leaf in allleaves(root)\n",
    "    v = hcat(collect(vertices(leaf.boundary))...)\n",
    "    plot!(plt, v[1,[1,2,4,3,1]], v[2,[1,2,4,3,1]])\n",
    "end\n",
    "plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 0.5.0",
   "language": "julia",
   "name": "julia-0.5"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "0.5.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
